#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

//class Date
//{
//public:
//	Date()
//	{
//		_year = 2024;
//		_month = 6;
//		_day = 15;
//	}
//	Date(const int year, const int month, const int day)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//
//	void Print()
//	{
//		cout << _year << '-' << _month << '-' << _day << endl;
//	}
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//int main()
//{
//	Date d1(1, 2, 3);
//	d1.Print();
//	return 0;
//}

#include <stdlib.h>
#include <stdbool.h>

typedef char DataType;
class Stack
{
public:
	Stack(int n = 4)
	{
		_arr = (DataType*)malloc(sizeof(DataType) * n);
		if (nullptr == _arr)
		{
			perror("malloc fail");
			exit(-1);
		}
		_capacity = n;
		_size = 0;
	}

	void Push(DataType x)
	{
		if (_capacity == _size)
			CreateSpace();

		_arr[_size] = x;
		_size++;
	}

	~Stack()
	{
		if (_arr)
			free(_arr);
		_arr = nullptr;
		_capacity = _size = 0;
	}

	DataType Top() { return _arr[_size - 1]; }
	void Pop() { _size--; }
	int Size() { return _size; }
	bool Empty() { return 0 == _size; }

private:
	void CreateSpace()
	{
		_capacity *= 2;
		DataType* tmp = (DataType*)realloc(_arr, sizeof(DataType) * _capacity);
		if (nullptr == tmp)
		{
			perror("realloc fail");
			exit(-2);
		}
		_arr = tmp;
	}

private:
	DataType* _arr;
	int _capacity;
	int _size;
};

bool isValid(const char* s)
{
	Stack st;

	while (*s)
	{
		if ('(' == *s || '[' == *s || '{' == *s)
			st.Push(*s);
		else
		{
			if (st.Empty())
				return false;
			char top = st.Top();
			st.Pop();

			if (('(' == top && ')' != *s) ||
				('[' == top && ']' != *s) ||
				('{' == top && '}' != *s))
				return false;
		}
		++s;
	}

	return st.Empty();
}

int main()
{
	const char* s = "(){{{}}}[[]]";
	cout << isValid(s) << endl;

	return 0;
}